package cn.mayday.algorithms.year2021.month1.C双指针专题;

import java.util.HashMap;
import java.util.Map;

/**
 * 剑指 Offer 48. 最长不含重复字符的子字符串
 *
 * @author: mayday
 * @date: 2021/5/11 20:30
 * @version: 1.0
 */
public class Offer048LengthOfLongestSubstring {

    public static void main(String[] args) {

    }

    /**
     * 采用：双指针 + 哈希表
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring1(String s) {
        // 保存指定字符串的索引位置
        Map<Character, Integer> map = new HashMap<>();

        // 【其中i，j双指针，哈希表用于保存最近出现的元素位置】

        int i = -1; // i记录上一次开始计算的索引【即左边界】
        int result = 0;
        for (int j = 0; j < s.length(); j++) {

            // 步骤一： 如果存在map中出现过两次，更新左边界i
            if (map.containsKey(s.charAt(j))) { // 说明j所在位置的字符串出现重复了，重新计算
                i = Math.max(i, map.get(s.charAt(j))); // 比较谁更大，取更大的更新左边界
            }

            // 步骤二 更新哈希表，保存指定字符出现的最后一个位置
            map.put(s.charAt(j), j);

            // 【步骤三】比较上次结果和这次结果，谁最大取谁
            result = Math.max(result, j - i);
        }
        return result;
    }

//    示例 1:
//
//    输入: s = "abcabcbb"
//    输出: 3
//    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

    // 方法二：滑动窗口方法
//    public int lengthOfLongestSubstring(String s) {
//
//        int result = 0;
//        for (int i = 0; i < s.length(); i++) {
//
//        }
//    }
}
